package com.example.demo.hot100;

/**
 * @Classname no11
 * @Description
 * @Date 2023/12/21 9:56
 * @Created by jyl
 *
 *
 * TODO  接雨水
 *
 * 给定n个非负整数a1，a2，...，an，其中每个点(i, ai)表示一个垂直线段。找到两条线，与x轴一起构成一个容器，使容器能容纳最多的水。
 *
 */
public class no11 {


    public static void main(String[] args) {

//		Vector<int> a = new Vector<int>(5);
        int[] a = new int[]{1,8,6,2,5,4,8,3,7};
        System.out.println(getMaxArea(a));

    }


    /****
     * 贪心法
     * 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
     * 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。
     * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     说明：你不能倾斜容器，且 n 的值至少为 2。
     输入: [1,8,6,2,5,4,8,3,7]
     输出: 49
     */
    public static int getMaxArea(int[] a){
        int hg = a.length;//数组长度
        int left = 0;
        int right = hg-1;
        //寻找最大面积
        int x = right - left + 1;//长方形的长度
        int y = Math.min(a[left], a[right]);
        int area = x*y;
        while(left != right){
            if(a[right] >= a[left]){//左边大于右边 每次要移动高度比较小的那个 才有可能让面积增大
                left = left + 1;
            }else{
                right = right - 1;
            }
            x = right - left;
            y = Math.min(a[left], a[right]);
            int temp = x*y;
            if(temp > area){
                area = temp;
            }
        }
        return area;
    }
}
